package leetcode.tree;

import java.util.Stack;
import java.util.TreeMap;

public class ValidateBinarySearchTree98 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution1 {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }

        public boolean isValidBST(TreeNode root, long min, long max) {
            if (root == null) {
                return true;
            }
            if (root.val <= min || root.val >= max) {
                return false;
            }
            return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
        }
    }

    class Solution2 {
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            Stack<TreeNode> stack = new Stack<>();
            long pre = Long.MIN_VALUE;
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    if (root.val <= pre) {
                        return false;
                    }
                    pre = root.val;
                    root = root.right;
                }
            }
            return true;
        }
    }

    class Solution3 {
        long cur = Long.MIN_VALUE;

        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            if (!isValidBST(root.left)) {
                return false;
            }
            if (cur >= root.val) {
                return false;
            }
            cur = root.val;
            if (!isValidBST(root.right)) {
                return false;
            }
            return true;
        }
    }

    class Solution {
        long pre = Long.MIN_VALUE;

        public boolean isValidBST(TreeNode root) {
          if (root == null) {
              return true;
          }
          if (!isValidBST(root.left)) {
              return false;
          }
          if (pre >= root.val) {
              return false;
          }
          pre = root.val;
          if (!isValidBST(root.right)) {
              return false;
          }
          return true;
        }
    }
}
